package com.sali.排序.raw;

/**
 * 分（Divide）：将数组递归分割为左右两个子数组，直到每个子数组长度为 1（自然有序）。
 * 治（Conquer）：合并两个有序的子数组，得到更大的有序数组，最终合并为整个有序数组。
 */
public class raw6_归并排序 {

    public static void main(String[] args) {
        int[] arr = new int[]{5, 4, 2, 3, 1};
        int[] temp = new int[arr.length];
        System.arraycopy(arr, 0, temp, 0, arr.length);
        mergetSort(arr, temp, 0, arr.length - 1);
        for (int element : arr) {
            System.out.print(element + " ");
        }
    }

    private static void mergetSort(int[] arr, int[] temp, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        mergetSort(arr, temp, left, mid);
        mergetSort(arr, temp, mid + 1, right);
        mySort(arr, temp, left, mid, right);
    }

    private static void mySort(int[] arr, int[] tmp, int left, int mid, int right) {
        int leftPoint = left;
        int rightPoint = mid + 1;
        int index = left;
        while ( leftPoint <= mid && rightPoint <= right ) {
            if ( arr[leftPoint] < arr[rightPoint] ) {
                tmp[index++] = arr[leftPoint++];
            } else {
                tmp[index++] = arr[rightPoint++];
            }
        }
        while ( leftPoint <= mid ) {
            tmp[index++] = arr[leftPoint++];
        }
        while ( rightPoint <= right ) {
            tmp[index++] = arr[rightPoint++];
        }
        for ( int i = left; i <= right; i++ ) {
            arr[i] = tmp[i];
        }
    }

}
